package com.justnow.solution;



public class Solution1 {

    /**
     * 方法一，单链表，没有头结点
     * @param head
     * @return
     */
    public static Node reverse(Node head) {

        if (head == null) {
            return head;
        }


        Node prevNode = head, currentNode = head.next;
        head.next = null;
        while (currentNode != null) {
            Node nextNode = currentNode.next;
            //第一步：将currentNode的next指向prev节点
            currentNode.next = prevNode;
            //第二步：将curretNode赋值给prevNode
            prevNode = currentNode;
            //第三步：将nextNode赋值给currentNode
            currentNode = nextNode;
        }
        return prevNode;
    }

    public static void display(Node head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
    }

    /**
     * 方法二，单链表没有头结点
     * @param head
     * @return
     */
    public static Node reverse2(Node head) {
        //pre = null的目的是让head的next指针为null，防止成环
        Node pre = null, cur = head;
        while(cur != null) {
            Node next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;//此时pre表示院原始链表的最后一个节点！
    }

    /**
     * 方法三，单链表有头节点
     *
     * 如：
     * dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
     * @param head
     * @return
     */
    public static Node reverse3(Node head) {
        if (head.next == null)
            return head;
        Node pre = head.next, current = head.next.next;
        pre.next = null;
        while (current != null) {
            Node temp = current.next;
            current.next = pre;
            pre = current;
            current = temp;
        }
        head.next = pre;
        return head;
    }


    public static void main(String[] args) {
        Node dumpy = new Node(-1);
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        dumpy.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        Node reverse3 = reverse3(dumpy);



        display(node1);
        Node reverse = reverse(node1);
        System.out.println("");
        display(reverse);
    }
}

class Node {
    int val;
    Node next;
    public Node(int val) {
        this.val = val;
    }
}